package Compation;

import java.util.*;

/**
 * 5414. 收藏清单
 * 给你一个数组 favoriteCompanies ，其中 favoriteCompanies[i] 是第 i 名用户收藏的公司清单（下标从 0 开始）。
 *
 * 请找出不是其他任何人收藏的公司清单的子集的收藏清单，并返回该清单下标。下标需要按升序排列。
 *
 *
 *
 * 示例 1：
 *
 * 输入：favoriteCompanies = [["leetcode","google","facebook"],["google","microsoft"],["google","facebook"],["google"],["amazon"]]
 * 输出：[0,1,4]
 * 解释：
 * favoriteCompanies[2]=["google","facebook"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 的子集。
 * favoriteCompanies[3]=["google"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 和 favoriteCompanies[1]=["google","microsoft"] 的子集。
 * 其余的收藏清单均不是其他任何人收藏的公司清单的子集，因此，答案为 [0,1,4] 。
 * 示例 2：
 *
 * 输入：favoriteCompanies = [["leetcode","google","facebook"],["leetcode","amazon"],["facebook","google"]]
 * 输出：[0,1]
 * 解释：favoriteCompanies[2]=["facebook","google"] 是 favoriteCompanies[0]=["leetcode","google","facebook"] 的子集，因此，答案为 [0,1] 。
 * 示例 3：
 *
 * 输入：favoriteCompanies = [["leetcode"],["google"],["facebook"],["amazon"]]
 * 输出：[0,1,2,3]
 *
 *
 * 提示：
 *
 * 1 <= favoriteCompanies.length <= 100
 * 1 <= favoriteCompanies[i].length <= 500
 * 1 <= favoriteCompanies[i][j].length <= 20
 * favoriteCompanies[i] 中的所有字符串 各不相同 。
 * 用户收藏的公司清单也 各不相同 ，也就是说，即便我们按字母顺序排序每个清单， favoriteCompanies[i] != favoriteCompanies[j] 仍然成立。
 * 所有字符串仅包含小写英文字母。
 */
public class peopleIndexes {
    public static void main(String[] args) {
        List<List<String>> favoriteCompanies = new ArrayList<>();
        String[][] input = new String[][] {{"leetcode","google","facebook"},
                {"google","microsoft"},
                {"google","facebook"},
                {"google"},
                {"amazon"}};
        for (int i = 0; i < input.length; i++) {
            favoriteCompanies.add(Arrays.asList(input[i]));
        }
        System.out.println(new peopleIndexes().peopleIndexesI(favoriteCompanies));
    }

    public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
        List<Integer> result = new ArrayList<>();
        if (favoriteCompanies == null || favoriteCompanies.size() == 0) {
            return result;
        }
        List<List<Integer>> inputToNum = new ArrayList<>();
        Map<String, Integer> stringToNum = new HashMap<>();
        int num = 0;
        for (int i = 0; i < favoriteCompanies.size(); i++) {
            List<Integer> subList = new ArrayList<>();
            for (String s: favoriteCompanies.get(i)) {
                if (stringToNum.containsKey(s)) {
                    subList.add(stringToNum.get(s));
                    continue;
                } else {
                    stringToNum.put(s, num);
                    subList.add(stringToNum.get(s));
                    num++;
                }
            }
            inputToNum.add(subList);
        }

        for (int i = 0; i < inputToNum.size(); i++) {
            boolean flag = true;
            for (int j = 0; j < inputToNum.size(); j++) {
                if (j == i) continue;
                if (Compare(inputToNum.get(i), inputToNum.get(j))) {
                    flag = false;
                    break;
                }
            }
            if(flag) result.add(i);
        }
        Collections.sort(result);
        return result;
    }

    /**
     * 用于比较s1是否为s2的子集，即s2是否包含s1
     * @param s1
     * @param s2
     * @return
     */
    public boolean Compare(List<Integer> s1, List<Integer> s2) {
        boolean flag = true;
        for (int i = 0; i < s1.size(); i++) {
            if (!s2.contains(s1.get(i))) {
                flag = false;
                break;
            }
        }
        return flag;
    }

    public List<Integer> peopleIndexesI(List<List<String>> favoriteCompanies) {
        List<Integer> result = new ArrayList<>();
        if (favoriteCompanies == null || favoriteCompanies.size() == 0) {
            return result;
        }
        for (int i = 0; i < favoriteCompanies.size(); i++) {
            boolean flag = true;
            for (int j = 0; j < favoriteCompanies.size(); j++) {
                if (i == j) continue;
                Set<String> firstSet = new HashSet<>(favoriteCompanies.get(i));
                Set<String> secondSet = new HashSet<>(favoriteCompanies.get(j));
                if (secondSet.containsAll(firstSet)) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                result.add(i);
            }
        }
        return result;
    }
}
